package sort;

import util.ArrayUtil;

import java.util.*;
import java.util.concurrent.ThreadLocalRandom;

/**
 * @author yuisama
 * @date 2023/03/30 20:08
 * 七大排序
 **/
public class SevenSort {
    private static ThreadLocalRandom random = ThreadLocalRandom.current();
    public static void main(String[] args) throws Exception{
        int n = 100_0000;
        int[] arr = ArrayUtil.generateRandomArray(n, 0, 50);
        int[] arr1 = ArrayUtil.arrCopy(arr);
        int[] arr2 = ArrayUtil.arrCopy(arr);
        int[] arr3 = ArrayUtil.arrCopy(arr);
        // 传入要测试的方法名称以及数组，就能调用该方法
        SortHelper.testSortMethod("quickSort",arr);
        SortHelper.testSortMethod("mergeSort",arr1);
        SortHelper.testSortMethod("quickSortHole",arr2);
        SortHelper.testSortMethod("quickSort3",arr3);

    }
    /**
     * 三路快排
     * 在一次操作中将所有重复元素一次放在最终位置
     * 最后只需要递归的在小于和大于v的子区间快排即可
     * @param arr
     */
    public static void quickSort3(int[] arr) {
        quickSortInternal3(arr,0,arr.length - 1);
    }
    /**
     * 三路快排
     * @param arr
     * @param l
     * @param r
     */
    private static void quickSortInternal3(int[] arr, int l, int r) {
        if (r - l <= 64) {
            insertionSort(arr,l,r);
            return;
        }
        int randomIndex = (int) (Math.random() * (r - l + 1)) + l;
        swap(arr,l,randomIndex);
        int v = arr[l];
        // arr[l + 1...lt] < v
        int lt = l;
        // arr[gt...r] > v
        int gt = r + 1;
        // arr[lt + 1..i) == v,i指向当前要处理的元素
        int i = l + 1;
        // 终止条件i和gt重合
        while (i < gt) {
            if (arr[i] < v) {
                swap(arr,lt + 1,i);
                lt ++;
                i ++;
            }else if (arr[i] > v) {
                // 此时不需要i++，因为gt-1这个未处理的元素换到i位置
                swap(arr,gt - 1,i);
                gt --;
            }else {
                // 此处arr[i] == v
                i ++;
            }
        }
        swap(arr,l,lt);
        // 交换后arr[l..lt - 1] < v ; arr[gt..r] >v
        quickSortInternal3(arr,l,lt - 1);
        quickSortInternal3(arr,gt,r);
    }
    // 算法4的分区快排
    public static void quickSort(int[] arr) {
        quickSortInternal(arr,0,arr.length - 1);
    }

    private static void quickSortInternal(int[] arr, int l, int r) {
        if (r - l <= 64) {
            insertionSort(arr,l,r);
            return;
        }
        int p = partition(arr,l,r);
        quickSortInternal(arr,l,p - 1);
        quickSortInternal(arr,p + 1,r);
    }

    private static int partition(int[] arr, int l, int r) {
        int randomIndex = random.nextInt(l,r);
        swap(arr,l,randomIndex);
        int v = arr[l];
        // arr[l + 1..j] < v
        int j = l;
        // arr[j + 1..i) >= v
        for (int i = l + 1; i <= r ; i++) {
            if (arr[i] < v) {
                swap(arr,j + 1,i);
                j ++;
            }
        }
        swap(arr,j,l);
        return j;
    }

    // 挖坑法快排
    public static void quickSortHole(int[] arr) {
        quickSortHoleInternal(arr,0,arr.length - 1);
    }

    /**
     * 在arr[l....r]进行快速排序
     * @param arr
     * @param l
     * @param r
     */
    private static void quickSortHoleInternal(int[] arr, int l, int r) {
        // base case
        // 优化1.小数组使用插入排序
        if (r - l <= 64) {
            insertionSort(arr,l,r);
            return;
        }
        int p = partitionByHole(arr,l,r);
        // 继续在两个子区间上进行快速排序
        quickSortHoleInternal(arr,l,p - 1);
        quickSortHoleInternal(arr,p + 1,r);
    }

    // 非递归的快排
    public static void quickSortNonRecursion(int[] arr) {
        // 借助栈
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(arr.length - 1);
        stack.push(0);
        while (!stack.isEmpty()) {
            int l = stack.pop();
            int r = stack.pop();
            if (l >= r) {
                // 当前这个子数组已经处理完毕
                continue;
            }
            int p = partitionByHole(arr,l,r);
            // 先将右半区间压入栈中
            stack.push(r);
            stack.push(p + 1);
            // 继续处理左半区间
            stack.push(p - 1);
            stack.push(l);
        }
    }

    private static int partitionByHole(int[] arr, int l, int r) {
        // 优化2.每次分区选择随机数作为分区点 : 避免快排在近乎有序的数组上退化为O(n^2)的复杂度
        int randomIndex = random.nextInt(l,r);
        swap(arr,l,randomIndex);
        int pivot = arr[l];
        int i = l,j = r;
        while (i < j) {
            // 先让j从后向前扫描碰到第一个 < pivot的元素终止
            while (i < j && arr[j] >= pivot) {
                j --;
            }
            arr[i] = arr[j];
            // 再让i从前向后扫描碰到第一个 > pivot的元素终止
            while (i < j && arr[i] <= pivot) {
                i ++;
            }
            arr[j] = arr[i];
        }
        // 回填分区点
        arr[j] = pivot;
        return j;
    }


    // 归并排序
    public static void mergeSort(int[] arr) {
        mergeSortInternal(arr,0,arr.length - 1);
    }
    // 在arr[l...r]进行归并排序
    private static void mergeSortInternal(int[] arr, int l, int r) {
        // base case
        // 优化2.小数组(64个元素以内)直接使用插入排序
        if (r - l <= 64) {
            insertionSort(arr,l,r);
            return;
        }
        // mid = (l + r) / 2
        int mid = l + ((r - l) >> 1);
        // 先将原数组一分为二，在子数组上先进行归并排序
        mergeSortInternal(arr,l,mid);
        mergeSortInternal(arr,mid + 1,r);
        // 此时两个子数组已经有序,将这两个子数组合并为原数组
        if (arr[mid] > arr[mid + 1]) {
            // 优化1.只有子数组1和子数组2存在元素的乱序才需要合并
            merge(arr,l,mid,r);
        }
    }
    // 在数组arr[l..r]上进行插入排序
    private static void insertionSort(int[] arr, int l, int r) {
        for (int i = l + 1; i <= r; i++) {
            for (int j = i; j > l && arr[j] < arr[j - 1]; j--) {
                swap(arr,j,j - 1);
            }
        }
    }

    private static void merge(int[] arr, int l, int mid, int r) {
        // 创建一个大小为r - l + 1的与原数组长度一样的临时数组aux
        int[] aux = new int[r - l + 1];
        System.arraycopy(arr,l,aux,0,r - l + 1);
        // 两个子数组的开始索引
        int i = l,j = mid + 1;
        // k表示当前原数组合并到哪个位置
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                // 子数组1全部拷贝完毕，将子数组2的所有内容协会arr
                arr[k] = aux[j - l];
                j ++;
            }else if (j > r) {
                // 子数组2全部拷贝完毕，将子数组1的剩余内容写回arr
                arr[k] = aux[i - l];
                i ++;
            }else if (aux[i - l] <= aux[j - l]) {
                // 稳定性
                arr[k] = aux[i - l];
                i ++;
            }else {
                arr[k] = aux[j - l];
                j ++;
            }
        }
    }


    // 选择排序
    public static void selectionSort(int[] arr) {
        // 起始状态 : 有序区间[0..i)
        // 无序区间[i....n)
        for (int i = 0; i < arr.length - 1; i++) {
            // min指向的当前无序区间的最小值
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            // 此时min一定指向无序区间最小值下标，换到无序区间的最开始位置
            swap(arr,i,min);
        }
    }
    // 希尔排序
    public static void shellSort(int[] arr) {
        int gap = arr.length >> 1;
        while (gap > 1) {
            // 先按照gap分组，组内使用插入排序
            insertionSortByGap(arr,gap);
            gap = gap >> 1;
        }
        // 当gap == 1时，整个数组接近于有序，此时来一个插入排序
        insertionSortByGap(arr,1);
    }

    // 按照gap分组，组内的插入排序
    private static void insertionSortByGap(int[] arr, int gap) {
        for (int i = gap; i < arr.length; i++) {
            for (int j = i; j - gap >= 0 && arr[j] < arr[j - gap] ; j -= gap) {
                swap(arr,j,j - gap);
            }
        }
    }

    // 直接插入排序
    public static void insertionSort(int[] arr) {
        // 无序区间[i...n)
        // 有序区间[0...i)
        // i指向当前无序区间的第一个元素
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j >= 1 && arr[j] < arr[j - 1]; j--) {
                swap(arr,j,j - 1);
//                if (arr[j] < arr[j - 1]) {
//                    swap(arr,j,j - 1);
//                }
            }
        }
    }

    // 无序区间[0...i]
    // 有序区间[]
    public static void bubbleSort(int[] arr) {
        // 外层循环表示要进行元素操作的趟数
        for (int i = 0; i < arr.length - 1; i++) {
            boolean isSwaped = false;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    isSwaped = true;
                    swap(arr,j,j + 1);
                }
            }
            if (!isSwaped) {
                break;
            }
        }
    }

    private static void swap(int[] arr,int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }




    // 原地堆排序
    public static void heapSort(int[] arr) {
        // 1.heapify
        for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
            siftDown(arr,i,arr.length);
        }
        // 不断的将当前无序数组的最大值(堆顶) 和 最后一个元素进行交换~
        for (int i = arr.length - 1; i >= 0; i--) {
            // 将堆顶(最大值) 和 i交换
            swap(arr,0,i);
            // 进行元素的下沉操作
            siftDown(arr,0,i);
        }
    }
    // 在数组arr上进行元素的下沉操作
    private static void siftDown(int[] arr, int k, int size) {
        int j = 2 * k + 1;
        while (j < size) {
            if (j + 1 < size && arr[j + 1] > arr[j]) {
                j = j + 1;
            }
            if (arr[k] >= arr[j]) {
                // 下沉结束
                break;
            }else {
                swap(arr,k,j);
                k = j;
                j = 2 * k + 1;
            }
        }
    }
}